Alternating Direction Method of Multipliers for A Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction

摘要

In this paper, we study a general optimization model, which covers a largeclass of existing models for many applications in imaging sciences. To solvethe resulting possibly nonconvex, nonsmooth and non-Lipschitz optimizationproblem, we adapt the alternating direction method of multipliers (ADMM) with ageneral dual step-size to solve a reformulation that contains three blocks ofvariables, and analyze its convergence. We show that for any dual step-sizeless than the golden ratio, there exists a computable threshold such that ifthe penalty parameter is chosen above such a threshold and the sequence thusgenerated by our ADMM is bounded, then the cluster point of the sequence givesa stationary point of the nonconvex optimization problem. We achieve this via apotential function specifically constructed for our ADMM. Moreover, weestablish the global convergence of the whole sequence if, in addition, thisspecial potential function is a Kurdyka-{\L}ojasiewicz function. Furthermore,we present a simple strategy for initializing the algorithm to guaranteeboundedness of the sequence. Finally, we perform numerical experimentscomparing our ADMM with the proximal alternating linearized minimization (PALM)proposed in [5] on the background/foreground extraction problem with real data.The numerical results show that our ADMM with a nontrivial dual step-size isefficient.